//用java语法提供的静态数组实现自己的数组
//使用泛型
public class Array<E> {

    //java语法提供的静态数组
    private E[] data;

    /*
    该数组的实际长度，操作数组这种数据结构关键就在于如何维护这个size
    size应该一直指向该数组中第一个没有元素的位置
     */
    private int size;

    /**
     *  带参构造
     *  capacity：数组最大长度
     */
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size=0;
    }

    //无参构造
    public Array(){
        /**
         *这一行不是java语法，这是这个idea编译器的提示
         * 表示调用带参构造传递capacity=10，方便我们看
         */
        this(10);
    }

    public Array(E[] arr){
        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];
        size = arr.length;
    }

    //得到数组中元素个数
    public int getSize(){
        return size;
    }
    //获取数组容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return  size==0;
    }

    //在数组末尾插入元素
    public void addLast(E e){
    /*    //在加入新的元素前，得先判断数组还有没有空间
            if(size == data.length){
            throw new IllegalArgumentException("addLast failed. Array is full.");
        }
        data[size]=e;
        //维护size
        size++;*/
    //也可以通过复用完成这个方法
        add(size,e);
    }

    //在数组头位置添加元素
    public void addFirst(E e){
        add(0,e);
    }

    //向数组中index位置插入元素
    public void add(int index, E e){

        //索引如果小于零不合法，索引大于size数据就不是连续的，中间会有没数据的地方
        if(index <0 || index > size){
            throw new IllegalArgumentException("add failed. Require index>=0 and index<=size.");
        }

        if(size == data.length) {
            //throw new IllegalArgumentException("add failed. Array is full.");
            //动态数组解决,让新的数组长度是原本数组长度的2倍，java的collection中是1.5倍
            resize(2 * data.length);
        }

        //从最末尾元素开始，依次往后移动，使后一个元素等于前一个元素的值，给index位置腾出空间
        for(int i =size-1 ; i>=index; i--){
                data[i+1] = data[i];
        }

        data[index]=e;
        //维护size
        size++;
    }


    //获取指定位置的元素
    public E get(int index){
        //这可以保证通过get这个方法，用户是无法使用没有值(无法使用)的空间的
        if(index < 0|| index >=size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    //修改指定位置元素
    public void set(int index , E e){
        if(index < 0|| index >=size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");

        data[index]=e;
    }

    //查找数组中是否有元素e
    public boolean contains(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i] == e)
                return true;
        }
        return false;
    }

    //查找数组中元素e所在的索引，如果不存在元素e，则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i] == e)
                return i;
        }
        return -1;
    };

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        //得到要被删除的元素
        E ret = data[index];
        //index后的元素每个往前移一个位置
        for(int i =index+1;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        // loitering objects != memory leak (闲逛数据不等于内存溢出)
        //数组的最后一位还是有值的，只是用户永远访问不到，但是这个数据还是存在的java的垃圾回收机制就不会去回收他
        //可以把他置为null，让回收机制能回收他
        data[size] = null;

        //当有一半的数组长度没使用到时，让数组的长度减半
        //避免复杂度震荡，让四分之三的数组长度没用到时，让速度的长度减半，避免addLast和removeLast在零界点依次调用反复触发resize
        if(size == data.length / 4 && data.length/2 != 0)
            resize(data.length / 2);
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
       return remove(size-1);
    }

    //从数组中删除元素e
    public void removeElement(E e){
        //找到这个元素的索引
        int index=find(e);
        remove(index);
    }

    //交换i 和 j两个元素
    public void swap(int i, int j){

        if(i < 0 || i >= size || j < 0 || j >= size)
            throw new IllegalArgumentException("Index is illegal.");

        E t = data[i];
        data[i] = data[j];
        data[j] = t;
    }


    //在java语法中，直接打印一个对象就是默认调用它的toString方法，这里我们进行重写，实现打印数组元素
    @Override
    public String toString(){
        StringBuilder res =new StringBuilder();
        //String.format 第一个参数是字符串格式，第二个参数是字符串格式中占位符的实际值
        res.append(String.format("Array:size=%d , capacity=%d\n",size,data.length));
        res.append("[");
        for(int i =0;i<size;i++){
            res.append(data[i]);
            if(i!=size-1)
                res.append(", ");
        }
        res.append("]");
        return res.toString();
    }

    public void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity];
        //把原本的数据拷贝进来
        for (int i =0;i<size;i++){
            newData[i]=data[i];
        }
        //让原先的data指向newData，这样其他方法在操作data的时候就是操作动态变化的这个数组了
        data = newData;

    }


}
